package 剑指专题.动态规划;


/*
 * Author：江松
 * Date：2023/3/21 19:07
 *
 矩阵覆盖：
 1，递归做法：搜索宽=2是固定的，可以搜索长度n，分别可以为1,2
 2,动态规划
 设dp(i)为长度为i时，的拼法
 从最后一步来想，可以分为2个状态
 dp(i)=dp(i-1)+dp(i-2)
 */

public class Main5 {
    public int rectCover(int target) {
        if(target==0)return 0;
        int a=1,b=1,ans=1;
        for(int i=2;i<=target;++i){
            ans=a+b;
            a=b;
            b=ans;
        }
        return ans;
    }
    /*
        int target;
        int ans;
        public void dfs(int now){
            if(now>target)return;
            if(now==target){
                ans++;
                return;
            }
            dfs(now+1);
            dfs(now+2);
        }
        public int rectCover(int target) {
            if(target==0)return 0;
            this.target=target;
            dfs(0);
            return ans;
        }
        */
}
